The cellular entry of HIV-1 to CD4+ T-cells requires ordered interactions of HIV-1-envelope glycoprotein with CXCR4 receptors. However, such interactions, which should be critical for rational structure-based discovery of new CXCR4 inhibitors, remain poorly understood. Herein, we first determined the effects of amino acid substitutions in CXCR4 on HIV-1NL4-3-glycoprotein-elicited fusion events using site-directed mutagenesis-based fusion assays and identified eleven potentially key amino acid substitutions, including D97A and E288A, which caused 30% reduction of the fusion. We subsequently carried out computational search of a screening library containing 604,000 compounds in order to identify potential CXCR4 inhibitors. The computational search used the shape of IT1t, a known CXCR4 inhibitor as a reference and employed various algorithms including shape similarity, isomer generation, and docking against a CXCR4 crystal structure. Sixteen small-molecules were identified for biological assays based on their high shape similarity to IT1t and their putative binding modes formed hydrogen bond interactions with amino acids identified above. Three compounds, having a piperidinylethanamine core, showed activity and were resynthesized. One molecule, designated CX6, was proven to significantly inhibit HIV-1NL4-3-glycoprotein-elicited fusion, inhibit SDF-1alpha-elicited Ca2+ flux (IC50:92 nM), and exert anti-HIV-1 activity. Structural modeling demonstrated that CX6 bound to CXCR4 through hydrogen-bond interactions with Asp97 and Glu288. Our study suggests that targeting CXCR4 residues important for HIV-1-envelope glycoprotein-elicited fusion should be a useful and practically feasible approach in identifying novel CXCR4 inhibitors and sheds important insights into the mechanism by which small-molecule CXCR4 inhibitors exert their anti-HIV-1 activity. As of this writing, Maraviroc, active against R5-HIV-1, is the only CCR5 inhibitor in clinical use. However, many infected patients carry R5-HIV-1 as well as X4-HIV-1 strains and no small molecule inhibitor specifically targeting CXCR4 is in clinical use. X4-HIV-1 may become predominant when HIV-1 disease progresses. Availability of a CXCR4 inhibitor would greatly increase the treatment options for patients infected with X4- and dual-tropic X4/R5-HIV-1. In vitro studies suggest that CCR5 and CXCR4 inhibitors together provide a greater synergistic effect, and CCR5 and CXCR4 inhibitors together as part of a drug cocktail has the potential to provide a greater benefit to patients. CCR5 has been more actively pursed as an anti-HIV-1 target as some patients with a natural deletion of the CCR5 gene are physiologically normal. CXCR4 belongs to the family of chemoattractant cytokines and may be functionally important for angiogenesis, angiostasis, embryogenesis, cancer and inflammatory diseases. This is by no means a comprehensive list of the functional importance of CXCR4, but indicates the challenges involved in developing a safe CXCR4 antagonist for clinical use. An ideal solution to CXCR4 inhibitor-induced toxicity would be to create a molecule that when bound to CXCR4 would prevent HIV-1 fusion, without interfering with normal CXCR4 function. Clinical trial of AMD3100 was discontinued for HIV-1 due to adverse toxicity even though it was approved to be used as a stem cell mobilizer. Besides discovering a molecule with a high therapeutic index, an optimum dosage might need to be determined. It is quite possible that having a specific dose of a CXCR4 inhibitor could lead to effective HIV mitigation, while minimizing toxicity. If these challenges are overcome, CXCR4 inhibitors may rapidly become assimilated to current HAART regimens. Besides inhibitors targeting CCR5 and CXCR4, inhibitors such as AR177 (Zintevir) that target gp120, and demonstrate anti-HIV activity have been reported. Virtually all inhibitors of CXCR4-gp120 interactions previously reported in the literature were discovered and optimized before the crystal structure became available. The crystal structure reported by Wu et al., showing an orthosteric binding site, opens up the possibility of discovering novel inhibitor chemotypes and rational optimization of inhibitors. We did a comprehensive examination of the effects of amino acid substitutions in the transmembrane and extracellular domains of CXCR4 on HIV-1-gp120-elicited cell fusion and identified eleven residues important for preserving the interaction of CXCR4 with the gp120 protein. We hypothesized that molecules that formed hydrogen bond interactions with at least two of these residues might competitively inhibit the interaction of CXCR4 and gp120 and exert antiviral activity. A general screening library was searched to identify molecules with a high three dimensional shape similarity to a known CXCR4 inhibitor and formed hydrogen bond interactions with at least two of these eleven residues. Using a computational search that took account of the residue-by-residue interaction analysis of CXCR4, we identified piperidinylethanamine derivatives as a novel antagonist family of CXCR4. The most promising PEA derivative inhibited SDF-1alpha-induced Ca2+ influx with CXCR4 in Molt4 cells with an IC50 of 76 nM, and exerted anti-HIV-1 activity with an IC50 value of 600 nM. The current study provides a platform for structure-based discovery of CXCR4 inhibitors. The study also sheds important insight into the mechanism of antiviral activity of inhibitors targeting CXCR4 and our approach may be useful in exploring antagonists against other novel targets by understanding the mechanism of action.